搜索算法－讲解[八皇后问题]

算法分析

深度优先搜索法。
首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出口出来。那老鼠会怎么走？当然是这样的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意选 择其中的一个继续往下走，如果遇到死胡同，就退回到最近的一个分叉路口，选择另一条道路再走下去，如果 遇到了出口，老鼠的旅途就算结束了。

深度优先搜索法的基本原则就是这样：按照某种条件往前试探搜索，如 果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到条件的目标为止。
实现这一算法，我们要用到编程的另一大利器--递归。

再举一个例子；从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚， 老和尚在讲故事，讲什么呢？讲：…………。好家伙，这样讲到世界末日还讲不玩，老和尚讲的故事实际上就 是前面的故事情节，这样不断地调用程序本身，就形成了递归。 万一这个故事中的某一个老和尚看这个故事不 顺眼，就把他要讲的故事换成：“你有完没完啊！”，这样，整个故事也就嘎然而止了。我们编程就要注意这 一点，在适当的时候，就必须要有一个这样的和尚挺身而出，把整个故事给停下来，或者使他不再往深一层次搜索，要不，我们的递归就会因计算机存储容量的限制而被迫溢出，切记，切记。
我们把递归思想运用到上面的迷宫中，记老鼠现在所在的位置是(x,y),那它现在有前后左右4个方向可以走，分别是(x+1,y),(x-1,y),(x,y+1),(x,y-1),其中一个方向是它来时的路，我们先不考虑，我们就分别尝试其他三个方向，如果某个方向是路而不是墙的话，老鼠就向那个方向迈出一步。在新的 位置上，我们又可以重复前面的步骤。老鼠走到了死胡同又是怎么回事？就是除了来时的路，其他3个方向都是墙，这时这条路就走到了尽头，无法再向深一层发展，我们就应该沿来时的路回去，尝试另外的方向。

例：八皇后问题：
8只皇后，使她们彼此互相都不能吃到对方，求皇后的放法。
这是一道很经典的题目了，如何运用深度优先搜索法，完成这道题目。我们先建立一个8*8格的棋盘，在棋盘的第一行的任意位置安放一只皇后。紧接着，我们就来放 第二行，第二行的安放就要受一些限制了，因为与第一行的皇后在同一竖行或同一对角线的位置上是不能安放皇后的，接下来是第三行……，或许我们会遇到这种情况，在摆到某一行的时候，无论皇后摆放在什么位置，她都会被其他行的皇后吃掉，这说明什么呢？这说明，我们前面的摆放是失败的，也就是说，按照前面的皇后的摆放方法，我们不可能得到正确的解。那这时怎么办？改啊，我们回到上一行，把原先我们摆好的皇后换另外一个位置，接着再回过头摆这一行，如果这样还不行或者上一行的皇后只有一个位置可放，那怎么办？我们回到上一行的上一行，这和老鼠碰了壁就回头是一个意思。就这样的不断的尝试，修正，尝试修正，我们最终会得到正确的结论的。

[参考程序]

program queen;{8皇后问题参考程序}
const n=8;
var a,b:array [1..n] of integer;{数组a存放解：a[i]表示第i个皇后放在第a[i]列；}
     c:array [1-n,n-1] of integer;
     d:array [2..n+n] of
integer;{数组b，c，d表示棋盘的当前情况：b[k]为1表示第k行已被占领为0表示为空；c、d表示对角线}
     k:integer;
procedure print;{打印结果}
var j:integer;
begin
           for j:=1 to n do write(a[j]:4);
           writeln;
end;
procedrue try(i:integer); {递归搜索解}
var
j:integer;{每个皇后的可放置位置。注意：一定要在过程中定义；否则当递归时会覆盖掉它的值，不能得到正确
结果}
begin
      for j:=1 to n do
      begin
           if (b[j]=0) and (c[i-j]=0) and    (d[i+j]=0) then{检查位置是否合法}
           begin
                a[i]:=j;{置第i个皇后的位置是第j行}
                b[j]:=1;{宣布占领行、对角线}
                c[i-j]:=1;
                d[i+j]:=1;
                if i<8 then try(i+1) else print;
                b[j]:=0;{清空被占行、对角线，回溯}
                c[i-j]:=0;
                d[i+j]:=0;
           end;
      end;
end;
begin
           for k:=1 to n do b[k]:=0;{初始化数据}
           for k:=1-n to n-1 do c[k]:=0;
           for k:=2 to n+n do d[k]:=0;
           try(1);
end.

Ｎ皇后问题
问题描述：
　　 在Ｎ*Ｎ的棋盘上，放置Ｎ个皇后，要求每一横行，每一列，每一对角线上均只能放置一个皇后，求可能的方案及方案数。

{
   Problem    : N Queens Problem
   Algorithm : Depth First Search
   Author     : tenshi
   Date       : 2002-07-14 @ SJTU ZZL 111
}
Program N_Queens;
const n=8;
var
   a:array[1..n] of integer;    { 皇后放在 ( i, a[i] ) }
   mk:array[1..n] of boolean; { 如果mk[i]为true，表示第i列可以放 }
   total:integer;              { 方案总数 }
  
   procedure output; {输出}
   var i:integer;
   begin
     inc(total);
     write('No.':4,'[',total:2,']');
     for i:=1 to n do write(a[i]:3);
     writeln;    
   end;
  
   function can(d:integer):boolean;   {判断第d行的Queen可否放在第a[d]列}
   var i:Integer;
   begin
     can:=false;
     if mk[a[d]] then exit; {如果第d列已经被占，则返回false}
     for i:=1 to d-1 do
       if abs(a[i]-a[d])=abs(i-d) then exit; { 如果第i行和第d行的Queen在同一对角线上，则返回false }
     can:=true;
   end;
  
   procedure dfs(d:integer);
   var i,j:integer;
   begin
     if (d>n) then   { 找到一个解并输出 }
     begin
       output;  
       exit;
     end;
     for i:=1 to N do    { 每一行均有N种放法 }
     begin
       a[d]:=i;           { 第d行的Queen放在第a[d]列 }
       if can(d) then
       begin
         mk[i]:=true;    { 标记第i列已经被占 }
         dfs(d+1);       { 如果第d行的方法可行，就放下一行 }
         mk[i]:=false;   { 恢复第i列被占标记 }
       end;                       
     end;
   end;
  
   begin
     fillchar(mk,sizeof(mk),0);
     dfs(1);
     writeln('Total = ',total);
   end.

                      

把Ｎ拆分为若干个数的和
问题描述：
　　给定一个正整数Ｎ，假设 0为Ｎ的一个拆封。现在要求Ｎ的拆分数目。例如：当Ｎ= 6 时
6 = 1 + 1 + 1 + 1 + 1 + 1
   = 1 + 1 + 1 + 1 + 2
   = 1 + 1 + 2 + 2
   = 2 + 2 + 2
   = 1 + 1 + 1 + 3
   = 1 + 2 + 3
   = 3 + 3
   = 1 + 1 + 4
   = 2 + 4
   = 1 + 5
   = 6
　　所以 6 的整数拆分个数为 11

{
   Problem    : N = A1 + A2 ... + As
   Algorithm : Depth First Search
   Author     : tenshi
   Date       : 2002-07-15 @ SJTU ZZL 111
}
Program N_Sum;
const n=6; 
var
   a:array[1..n] of integer;   { 保存单个拆分。n最多拆封为n个1，所以s<=n }
   total:integer;              { 方案总数 }
  
   procedure output(s:integer); { 输出。 s为一个拆分的长度 }
   var i:integer; 
   begin 
     write(n,' =',a[1]:3); 
     for i:=2 to s do write(' +',a[i]:3);
     writeln;    
   end; 
  
  
   procedure dfs(d,low,rest:integer);    { low为当前a[d]的下界,rest为还剩下多少要拆分 }
   var i:integer; 
   begin 
     if(rest=0) then {找到一组解}
     begin
       inc(total);
       output(d-1);
     end;
     if( low>rest ) then exit;
     {rest已经不能满足low的要求了，所以退出}
     for i:=low to rest do
     begin
       a[d]:=i;
       dfs(d+1,i,rest-i);
     end;
   end; 
  
   begin 
     dfs(1,1,n);
     writeln('Total = ',total); 
   end.